package master;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author chenyw
 * @date 2022/8/19 19:24
 */
public class M145postorderTraversal {
    public List<Integer> postorderTraversal(TreeNode root) {
         if (root == null) {
             return new ArrayList<>();
         }
         List<Integer> res = new ArrayList<>();
         Deque<TreeNode> stack = new LinkedList<>();
         TreeNode pre = null;
         while (root != null || !stack.isEmpty()) {
             while (root != null) {
                 stack.push(root);
                 root = root.left;
             }
             root = stack.pop();
             if (root.right == null || root.right == pre) {
                 res.add(root.val);
                 pre = root;
                 root = null;
             } else {
                 stack.push(root);
                 root = root.right;
             }
         }
         return res;
    }
}
